package com.zlk.algorithm.dataStructure.graph.traverse;

import com.zlk.algorithm.dataStructure.graph.impl.Graph;
import com.zlk.algorithm.dataStructure.graph.impl.Node;
import org.junit.Test;

import java.util.*;

/**
 * @program: algorithm
 * @ClassName Bfs
 * @description: 宽度优先遍历,类似于二叉树的层序遍历 ，一个队列一个set
 * @author: slfang
 * @create: 2024-03-15 17:03
 * @Version 1.0
 **/
public class BFS {

    /**
     * 对于连通图
     * @param start
     */
    public void bfs(Node start){
        if(start==null){
            return ;
        }
        Queue<Node> queue = new LinkedList<>();
        HashSet<Node> set = new HashSet<>();
        queue.add(start);
        while (!queue.isEmpty()){
            Node node = queue.poll();
            System.out.println(node.value);
            for (Node next : node.nexts) {
                if(!set.contains(next)){
                    queue.add(next);
                    set.add(next);
                }
            }
        }
    }

    @Test
    public void test() {
        Graph graph = new Graph();
        Node node1 = new Node(1);
        Node node21 = new Node(2);
        Node node22 = new Node(2);
        Node node31 = new Node(3);
        Node node41 = new Node(4);

        ArrayList<Node> list1 = new ArrayList();
        ArrayList<Node> list2 = new ArrayList();
        ArrayList<Node> list3 = new ArrayList();
        list1.add(node21);
        list1.add(node22);
        node1.nexts = list1;

        list2.add(node31);
        list3.add(node41);


        node22.nexts = list2;
        node31.nexts = list3;
        bfs(node1);


    }




}
